﻿using System.Collections.Generic;
using Lists = Algoritmia.DataStructures.Lists;
using System.Linq;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Geometry.ConvexHull
{
    public class QuickhullFinder
    {
        public IEnumerable<Point2D> Quickhull(Lists.IList<Point2D> S)
        {
            if (S.Count <= 2)
            {
                return S.ToList();
            }
            var p = S.Min();
            var q = S.Max();
            var z1 = S.Where(z => !z.Equals(p)  &&
                                  !z.Equals(q) &&
                                  Utils.Left(p, q, z)).ToAlgoritmiaList();
            var z2 = S.Where(z => !z.Equals(p)  &&
                                  !z.Equals(q)  &&
                                  Utils.Right(p, q, z)).ToAlgoritmiaList();

            var first = PrivateQuickhull(p, z1, q).Skip(1);
            var second = PrivateQuickhull(q, z2, p).Skip(1);
            return first.Concat(second);
        }

        public static IEnumerable<Point2D> PrivateQuickhull(Point2D a, Lists.IList<Point2D> A, Point2D b)
        {
            if (A.Count == 0)
            {
                return new[] {a, b};
            }
            var h = A.ArgMax(z => Utils.TriangleArea(a, b, z));
            var left =
                PrivateQuickhull(a, A.Where(z => Utils.Left(a, h, z)).ToAlgoritmiaList(), h);
            var right =
                PrivateQuickhull(h, A.Where(z => Utils.Left(h, b, z)).ToAlgoritmiaList(), b).Skip(1);
            return left.Concat(right);
        }
    }
}
